#pragma once

// https://leetcode.cn/problems/IlPe0q/

/*剑指 Offer II 100. 三角形中最小路径之和
给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1
*/

#include "../Base/CommTool.h"

namespace MinimunTotal
{
    class Solution
    {
    public:
        int minimumTotal(vector<vector<int>> &triangle)
        {
            if (triangle.empty())
                return 0;

            if(triangle.size() == 1)
                return triangle.back().front();

            vector<int> result = triangle.back();
            for (int i = triangle.size() - 2; i >= 0; --i)
            {
                for (size_t j = 0; j < triangle[i].size(); ++j)
                {
                    int curr = triangle[i][j];
                    if(result[j] < result[j + 1] )
                    {
                        result[j] = curr + result[j];
                    }
                    else
                    {
                        result[j] = curr + result[j+1];
                    }
                }
            }

            return result.front();
        }
    };
    
    void Test()
    {
        Solution solv;

        vector<vector<int>> triangle{
            {2},
            {3, 4},
            {6, 5, 2},
            {7, 5, 3, 1},
            {10, 8, 2, 4, 6}};

        cout << solv.minimumTotal(triangle) << endl;

        triangle = {
            {2},
            {3, 4},
            {6, 5, 7},
            {4, 1, 8, 3}};

        cout << solv.minimumTotal(triangle) << endl;
    }
}